#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "entropy.h"




float h_information_gain(List<FeatureTerm> *dset,List<FeatureTerm> *dsolutions,List<FeatureTerm> *solutions,FeatureTerm *current_description,int *coverage)
{
	List<FeatureTerm> *dset_tmp;
	List<FeatureTerm> *dsolutions_tmp;
	List<FeatureTerm> l;
	FeatureTerm *description,*s1,*s2;
	int nsols=solutions->Length();;
	int *distributiona=new int[nsols];
	int *distributionb=new int[nsols];
	int *distributionc=new int[nsols];
	int na,nb,nc;
	int i;
	float gain;

	na=dset->Length();

	for(i=0;i<nsols;i++) {
		s1=solutions->operator [](i);

		distributiona[i]=0;
		l.Instance(*dsolutions);
		l.Rewind();
		while(l.Iterate(s2)) if (*s1==*s2) distributiona[i]++;
	} /* for */  

	dset_tmp=new List<FeatureTerm>;
	dsolutions_tmp=new List<FeatureTerm>;

	dset->Rewind();
	dsolutions->Rewind();
	while(dset->Iterate(description) &&
		  dsolutions->Iterate(s1)) {
		if (current_description->subsumes(description)) {
			dset_tmp->Add(new FeatureTerm(description));
			dsolutions_tmp->Add(new FeatureTerm(s1));
		} /* if */ 
	} /* while */ 

	*coverage=dset_tmp->Length();

	for(i=0;i<nsols;i++) {
		s1=solutions->operator [](i);
		distributionb[i]=0;
		l.Instance(*dsolutions_tmp);
		l.Rewind();
		while(l.Iterate(s2)) if (*s1==*s2) distributionb[i]++;
		distributionc[i]=distributiona[i]-distributionb[i];
	} /* for */  

	nb=dset_tmp->Length();
	nc=na-nb;

	delete dset_tmp;
	delete dsolutions_tmp;

	/* Compute information gain: */ 
	{
		float e1,e2,e3;

		e1=entropy(nsols,distributiona);
		e2=entropy(nsols,distributionb);
		e3=entropy(nsols,distributionc);

		gain=e1-((float(nb)/float(na))*e2 + (float(nc)/float(na))*e3);
	}
/*
	{
		printf("[ ");
		for(i=0;i<nsols;i++) {
			printf("%i ",distributiona[i]);
		} // for  
		printf("] -> [ ");
		for(i=0;i<nsols;i++) {
			printf("%i ",distributionb[i]);
		} // for  
		printf("| ");
		for(i=0;i<nsols;i++) {
			printf("%i ",distributionc[i]);
		} // for  
		printf("] -> %g\n",gain);
	}
*/
	delete distributiona;
	delete distributionb;
	delete distributionc;

	return gain;
} /* h_information_gain */ 


float entropy(int l,int *d)
{
	int i;
	int total=0;
	float entropy=0;
	float tmp;
#ifndef M_LOG2E
	double M_LOG2E=log(2.0);
#endif

	for(i=0;i<l;i++) total+=d[i];

	for(i=0;i<l;i++) {
		tmp=float(d[i])/float(total);
		if (tmp!=0.0) {
			entropy+=float(tmp*(log(tmp)/M_LOG2E));
		} /* if */ 
	} /* for */ 

	return -entropy;
} /* entropy */ 



float h_rldm(List<FeatureTerm> *dset,List<FeatureTerm> *dsolutions,List<FeatureTerm> *solutions,FeatureTerm *current_description,int *coverage)
{
	List<FeatureTerm> ls,ld;
	FeatureTerm *description,*solution;
	int nsols=solutions->Length();
	int sol_pos;
	float rldm;
	int *d_correcta=new int[nsols];
	int *d_b=new int[2];
	int *d_intersection=new int[nsols*2];
	float e1,e2,e3;
	int i;

	for(i=0;i<nsols;i++) d_correcta[i]=0;
	for(i=0;i<2;i++) d_b[i]=0;
	for(i=0;i<2*nsols;i++) d_intersection[i]=0;

	ld.Instance(*dset);
	ls.Instance(*dsolutions);
	ld.Rewind();
	ls.Rewind();
	while(ld.Iterate(description) && ls.Iterate(solution)) {
		sol_pos=solutions->Position(solution);

		d_correcta[sol_pos]++;

		if (current_description->subsumes(description)) {
			d_b[0]++;
			d_intersection[sol_pos]++;
		} else {
			d_b[1]++;
			d_intersection[sol_pos+nsols]++;
		} /* if */ 
	} /* while */ 

	*coverage=d_b[0];

	/* Compute rldm: */ 
	{
		e1=entropy(nsols,d_correcta);
		e2=entropy(2,d_b);
		e3=entropy(2*nsols,d_intersection);

//		printf("A: ");for(i=0;i<nsols;i++) printf("%i ",d_correcta[i]);printf("\n");
//		printf("B: ");for(i=0;i<2;i++) printf("%i ",d_b[i]);printf("\n");
//		printf("C: ");for(i=0;i<2*nsols;i++) printf("%i ",d_intersection[i]);printf("\n");

//		printf("[%i] {%g %g %g} ",dsolutions->Length(),e1,e2,e3);

		if (e2==0) rldm=1;
			  else rldm=2.0F-((e1+e2)/e3);
	}

/*
	{
		printf("[ ");
		for(i=0;i<nsols;i++) {
			printf("%i ",d_correcta[i]);
		} // for  
		printf("] -> [ ");
		for(i=0;i<2;i++) {
			printf("%i ",d_b[i]);
		} // for  
		printf("| ");
		for(i=0;i<2*nsols;i++) {
			printf("%i ",d_intersection[i]);
		} // for  
		printf("] -> %g\n",1-rldm);
	}
*/

	delete []d_correcta;
	delete []d_b;
	delete []d_intersection;

	return rldm;
} /* h_rldm */ 


float h_entropy(List<FeatureTerm> *dset,List<FeatureTerm> *dsolutions,List<FeatureTerm> *solutions,FeatureTerm *current_description,int *coverage)
{
	List<FeatureTerm> *dset_tmp;
	List<FeatureTerm> *dsolutions_tmp;
	List<FeatureTerm> l;
	FeatureTerm *description,*s1,*s2;
	int nsols=solutions->Length();;
	int *distributionb=new int[nsols];
	int na,nb,nc;
	int i;
	float e;

	na=dset->Length();

	dset_tmp=new List<FeatureTerm>;
	dsolutions_tmp=new List<FeatureTerm>;

	dset->Rewind();
	dsolutions->Rewind();
	while(dset->Iterate(description) &&
		  dsolutions->Iterate(s1)) {
		if (current_description->subsumes(description)) {
			dset_tmp->Add(new FeatureTerm(description));
			dsolutions_tmp->Add(new FeatureTerm(s1));
		} /* if */ 
	} /* while */ 

	*coverage=dset_tmp->Length();

	for(i=0;i<nsols;i++) {
		s1=solutions->operator [](i);
		distributionb[i]=0;
		l.Instance(*dsolutions_tmp);
		l.Rewind();
		while(l.Iterate(s2)) if (*s1==*s2) distributionb[i]++;
	} /* for */  

	nb=dset_tmp->Length();
	nc=na-nb;

	delete dset_tmp;
	delete dsolutions_tmp;

	/* Compute information gain: */ 
	{
		float e2;

		e2=entropy(nsols,distributionb);

		e=e2;
	}
/*
	{
		printf("[ ");
		for(i=0;i<nsols;i++) {
			printf("%i ",distributiona[i]);
		} // for  
		printf("] -> [ ");
		for(i=0;i<nsols;i++) {
			printf("%i ",distributionb[i]);
		} // for  
		printf("| ");
		for(i=0;i<nsols;i++) {
			printf("%i ",distributionc[i]);
		} // for  
		printf("] -> %g\n",gain);
	}
*/
	delete distributionb;

	return e;
} /* h_entropy */ 
